Evaluating User Effectiveness in Exploratory Search with TouchGraph Google Interface.

Simulation Modeling Movable Hospital Assets Managed with RFID Sensors.

A User Interface for Exploiting Web Communities in Searching the Web.

Embedding complete binary trees in product graphs.

Speedup and Scalability of SPMD Computations on Workstation Clusters.

Speedup and Scalability of SPMD Computations on Workstation Clusters.

An Optimal Emulator and VLSI Layout for Complete Binary Trees.

Efficient VLSI Layouts for Homogeneous Product Networks.
In this paper we develop generalized methods to layout homogeneous product networks with  any number of dimensions, and analyze their VLSI complexity by deriving upper and lower  bounds on the area and maximum wire length.  In the literature, lower bounds are generally obtained by computing lower bounds on the  bisection width or the crossing number of the network being laid out. In this paper we define a  new measure that we call &#034;maximal congestion,&#034; that can be used to obtain both the bisection  width and the crossing number, thereby unifying the two approaches. Upper bounds are traditionally  obtained by constructing layouts based on separators or bifurcators. Both methods  have the basic limitation that they are applicable only for graphs with bounded vertex degree.  The separators approach generally yields good layouts when good separators can be found, but  it is difficult to find a good separator for an arbitrary graph. The bifurcators approach is easier  to apply, but it gener...
Generalized Algorithm for Parallel Sorting on Product Networks.
We generalize the well-known odd-even merge sorting algorithm originally due to  Batcher [2], and show how this generalized algorithm can be applied to sorting on  product networks.  If G is an arbitrary factor graph with N nodes, its r-dimensional product contains  N  r  nodes. Our algorithm sorts N  r  keys stored on the r-dimensional product of G in  O(r  2  F (N)) time, where F (N) depends on G. We show that for any factor graph G,  F (N) is at most O(N ), establishing an upper bound of O(r  2  N) for the time complexity  of sorting N  r  keys on any product network.  When r is bounded, this leads to the asymptotic complexity O(N) to sort N  r  keys,  which is optimal for several instances of product networks. There are factor graphs for  which F (N) = O(log  2  N ), which leads to the asymptotic running time of O(log  2  N) to  sort N  r  keys. When N is bounded (e.g. in the hypercube) the asymptotic complexity  becomes O(r  2  ).  We show how to apply the algorithm to several cas...
Embedding Complete Binary Trees in Product Graphs.

Effective queueing strategies for co%2Dscheduling in a pool of processors.

Mesh%2DConnected Trees A Bridge Between Grids and Meshes of Trees.
The grid and the mesh of trees (or MOT) are among the best-known parallel architectures in the  literature. Both of them enjoy efficient VLSI layouts, simplicity of topology, and a large number of  parallel algorithms that can efficiently execute on them. One drawback of these architectures is that  algorithms that perform best on one of them do not perform very well on the other. Thus there is a gap  between the algorithmic capabilities of these two architectures.  We propose a new class of parallel architectures, called the mesh-connected trees (or MCT) that can  execute grid algorithms as efficiently as the grid, and MOT algorithms as efficiently as the MOT, up  to a constant amount of slowdown. In particular, the MCT topology contains the MOT as a subgraph  and emulates the grid via embedding with dilation 3 and congestion 2. This significant amount of  computational versatility offered by the MCT comes at no additional VLSI area cost over these earlier  networks. Many topological,...
Generalized Algorithm for Parallel Sorting on Product Networks.
We generalize the well-known odd-even merge sorting algorithm originally due to  Batcher [2], and show how this generalized algorithm can be applied to sorting on  product networks.  If G is an arbitrary factor graph with N nodes, its r-dimensional product contains  N  r  nodes. Our algorithm sorts N  r  keys stored on the r-dimensional product of G in  O(r  2  F (N)) time, where F (N) depends on G. We show that for any factor graph G,  F (N) is at most O(N ), establishing an upper bound of O(r  2  N) for the time complexity  of sorting N  r  keys on any product network.  When r is bounded, this leads to the asymptotic complexity O(N) to sort N  r  keys,  which is optimal for several instances of product networks. There are factor graphs for  which F (N) = O(log  2  N ), which leads to the asymptotic running time of O(log  2  N) to  sort N  r  keys. When N is bounded (e.g. in the hypercube) the asymptotic complexity  becomes O(r  2  ).  We show how to apply the algorithm to several cas...
Embedding Large Complete Binary Trees in Hypercubes with Load Balancing.

Generalized Algorithm for Parallel Sorting on Product Networks.
We generalize the well-known odd-even merge sorting algorithm originally due to  Batcher [2], and show how this generalized algorithm can be applied to sorting on  product networks.  If G is an arbitrary factor graph with N nodes, its r-dimensional product contains  N  r  nodes. Our algorithm sorts N  r  keys stored on the r-dimensional product of G in  O(r  2  F (N)) time, where F (N) depends on G. We show that for any factor graph G,  F (N) is at most O(N ), establishing an upper bound of O(r  2  N) for the time complexity  of sorting N  r  keys on any product network.  When r is bounded, this leads to the asymptotic complexity O(N) to sort N  r  keys,  which is optimal for several instances of product networks. There are factor graphs for  which F (N) = O(log  2  N ), which leads to the asymptotic running time of O(log  2  N) to  sort N  r  keys. When N is bounded (e.g. in the hypercube) the asymptotic complexity  becomes O(r  2  ).  We show how to apply the algorithm to several cas...
Optimal Scheduling of Compute%2DIntensive Tasks on a Network of Workstations.

Products of Networks with Logarithmic Diameter and Fixed Degree.
This paper first presents some general properties of product networks pertinent to parallel architectures  and then focuses on three case studies. These are products of complete binary trees,  shuffle-exchange, and de Bruijn networks. It is shown that all of these are powerful architectures  for parallel computation, as evidenced by their ability to efficiently emulate numerous other architectures.  In particular, r-dimensional grids, and r-dimensional meshes of trees can be embedded  efficiently in products of these graphs, i.e. either as a subgraph or with small constant dilation and  congestion. In addition, the shuffle-exchange network can be embedded in r-dimensional product  of shuffle exchange networks with dilation cost 2r and congestion cost 2. Similarly, the de Bruijn  network can be embedded in r-dimensional product of de Bruijn networks with dilation cost r and  congestion cost 4. Moreover, it is well known that shuffle-exchange and de Bruijn graphs can emulate  the hypercu...
Computational Properties of Mesh Connected Trees Versatile Architectures for Parallel Computation.
Recently, the mesh connected trees (MCT) network has been proposed asapossible architecture for parallel computers. MCT networks are obtained bycombining complete binary trees using the cross product operation. This paper focuses on structural, embedding, routing, and layout properties of the MCT networks. We show that MCT networks are computationally more powerful than grids and complete binary trees, and at least as powerful as meshes of trees (MOT). Analysis of VLSI complexity shows that the additional power is obtained without asymptotically increasing the layout area withrespect to the grid of at least 3 dimensions or to the MOT of any number of dimensions. A variation of the basic architecture with same maximum vertex degree and same asymptotic area complexity is also investigated. This variation contains the torus as a subgraph as well as the MOT, further increasing the computational power of the basic architecture. These results suggest that the basic MCT network and its variant are suitable architectures for a large class of massively parallel computations.
Queueing performance analysis of co%2Dscheduling in a pool of processors environment.

Topological Properties of the Crossed Cube Architecture.

Topological Properties of the Crossed Cube Architecture.

Performance of Co%2DScheduling on a Network of Workstations.

Embedding Large Mesh of Trees and Related Networks in the Hypercube With Load Balancing.

Reconfigurable Cube Architecture for Parallel Computation.

The Crossed Cube Architecture for Parallel Computation.

Load balancing with network cooperation.

Congestion and Fault Tolerance of Binary Tree Embeddings on Hypercube.

An analytical model for predicting performance in a heterogeneous system.

A Variation on the Hypercube with Lower Diameter.

Embedding Mesh of Trees in the Hypercube.
Embedding one architecture in another is useful in providing architectural abstractions between different topologies. Through such embeddings the algorithms originally developed for one architecture can he directly mapped to another architecture. This paper describes methods for embedding one-, two-, and three-dimensional mesh of trees in the hypercube. Similar methods may be used for embedding higher-dimensional mesh of trees. This embedding has significant practical importance in enhancing the capabilities of the hypercuhe since mesh of trees enable extremely fast parallel computation.  
Embedding Mesh of Trees in the Hypercube.
Embedding one architecture in another is useful in providing architectural abstractions between different topologies. Through such embeddings the algorithms originally developed for one architecture can he directly mapped to another architecture. This paper describes methods for embedding one-, two-, and three-dimensional mesh of trees in the hypercube. Similar methods may be used for embedding higher-dimensional mesh of trees. This embedding has significant practical importance in enhancing the capabilities of the hypercuhe since mesh of trees enable extremely fast parallel computation.  
Heuristic Algorithms for Adaptive Load Sharing in Local Networks.

A Proposed Solution to the Problem of Levels in Error%2DMessage Generation.

A Proposed Solution to the Problem of Levels in Error%2DMessage Generation.

